package avltree;


public class AVLTree {

    static class TreeNode{
        public int val;
        public int bf;//平衡因子
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;

        public TreeNode(int val){
            this.val = val;
        }

    }

    public TreeNode root;//根节点

    //插入
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if (root==null){
            root = new TreeNode(val);
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur!=null){
            if (cur.val<val){
                parent  = cur;
                cur = cur.right;
            }else if(cur.val == val){
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }

        //cur == null
        if (parent.val<val){
            parent.right = node;
        }else{
            parent.left = node;
        }

        //选择平衡二叉树
        node.parent = parent;
        cur = node;


        //调节平衡因子
        while (parent!=null){
            //先看cur是parent的左还是右，决定平衡因子是++ 还是 --
            if (cur == parent.right){
                //如果是右树，右树高度增加，平衡因子++
                parent.bf++;
            }else{
                //如果是左树，左树的高度增加，平衡因子--
                parent.bf--;
            }

            //检验当前的平衡因子是不是 1 0 -1
            if (parent.bf==0){
                //说明已经平衡
                break;
            }else if(parent.bf==1 || parent.bf==-1){
                //继续向上修改平衡因子
                cur = parent;
                parent = cur.parent;
            }else{
                if (parent.bf == 2){//右树高，降低右树的高度
                    if (cur.bf == 1){
                        //左旋
                        rotateLeft(parent);
                    }else{
                        //cur.bf==-1
                        //右左双旋
                        rotateRL(parent);
                    }
                }else{//左树高，降低左树的高速
                    //parent.bf == -2
                    if (cur.bf == -1){
                        //右旋
                        rotateRight(parent);
                    }else{
                        //先左旋再右旋
                        rotateLR(parent);
                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }

        return true;
    }

    //先右旋再左旋
    private void rotateRL(TreeNode parent) {

        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        //调节平衡因子
        if (bf == 1){
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subR.bf = 0;
            subRL.bf = 1;
        }


    }

    //先左旋，再右旋
    private void rotateLR(TreeNode parent) {

        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        rotateLeft(parent.left);
        rotateRight(parent);
        //修改平衡因子
        if (bf == -1){
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }


    }

    //左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        //旋转
        parent.right = subRL;
        subR.left = parent;
        if (subRL !=null){
            subRL.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subR;

        //判断根节点
        if (root == parent){
            root = subR;
            root.parent = null;
        }else{
            if (pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }

        //修改平衡因子
        subR.bf = 0;
        parent.bf = 0;



    }

    //右旋
    private void rotateRight(TreeNode parent) {

        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        //右旋
        parent.left = subLR;
        subL.right =  parent;
        if (subLR!=null){//没有subL的时候
            subLR.parent = parent;
        }
        //先记录parent 的 parent
        TreeNode pParent = parent.parent;
        parent.parent = subL;

        //检查当前是不是根节点
        if (parent == root){
            root = subL;
            root.parent = null;
        }else{
            //不是根节点判断这个子树是左子树还是右子树
            if (pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }

        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }



    //中序遍历
    public void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }
    private int height(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH>rightH?leftH+1:rightH+1;

    }

    public boolean isBalance(TreeNode root) {
        if (root == null){
            return true;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH-leftH!=root.bf){
            System.out.println("这个节点"+root.val+"平衡因子异常");
            return false;
        }

        return Math.abs(leftH - rightH)<=1
                && isBalance(root.left)
                && isBalance(root.right);


    }









}
